//题目：
// 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
#include<iostream>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int numDistinct(string s, string t) 
    {
        int n1=t.size(),n2=s.size();
        s=" "+s,t=" "+t;
        //1.创建dp表————dp[i][j]表示：t的[0,i]区间子字符串，在s[0,j]区间中相同的子序列的个数
        vector<vector<int>> dp(n1+1,vector<int>(n2+1));
        //2.初始化————虚拟行、列和占位空格
        for(int i=0;i<n2+1;i++)
            dp[0][i]=1;
        //3.填表
        for(int i=1;i<n1+1;i++)
        {
            for(int j=1;j<n2+1;j++)
            {
                dp[i][j]=dp[i][j-1];
                if(t[i]==s[j])
                    dp[i][j]+=dp[i-1][j-1];
                dp[i][j]%=1000000007;
            }
        } 
        return dp[n1][n2];
    }
};